import java.util.ArrayList;
import java.util.Stack;

class ListNode {
    int val;
   ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

 class TreeNode {
   int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
}

public class Test {
    /**
     * 判断是否为回文链表
     * @param head ListNode类 链表头
     * @return bool布尔型
     */
    public static boolean isPalindrome (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return false;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        cur = head;
        while(!stack.isEmpty()) {
            ListNode tmp = stack.pop();
            if(tmp.val != cur.val) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }
    public static boolean isCompleteTree (TreeNode root) {
        // write code here
        int ret = getHeight(root);
        if(ret == -1) {
            return false;
        }
        return true;
    }

    private static int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        if(leftHeight == -1 || rightHeight == -1) {
            return -1;
        }

        if(Math.abs(leftHeight-rightHeight) > 1) {
            return -1;
        }

        return Math.max(leftHeight,rightHeight) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode root1 = new TreeNode(0);
        TreeNode root2 = new TreeNode(0);
        TreeNode root3 = new TreeNode(0);

        root.left = root1;
        root1.right = root2;
        root1.left = root3;

        System.out.println(isCompleteTree(root));
        ArrayList<Integer> list = new ArrayList<>();
    }

    public static void main1(String[] args) {
        ListNode head = new ListNode(1);
        System.out.println(isPalindrome(head));

    }
}